def egcd(a, b):
 if (a == 0):
     return [b, 0, 1]
 else:
     g, y, x = egcd(b % a, a)
     return [g, x - (b // a) * y, y]

# Modular multiplicative inverse
def modInv(a, m):
 g, x, y = egcd(a, m)
 if (g != 1):
     raise Exception("[-]No modular multiplicative inverse of %d under modulus %d" % (a, m))
 else:
     return x % m


pstr = "57712671469 * 79753565033 * 91838820179 * 156135349637 * 299708689207 * 457408060411 * 476875578869 * 495070766849 * 539156063617 * 547718265481 * 578072728433 * 624533069099 * 672942390979 * 677437074187 * 748151626433 * 752501396681 * 815527664663 * 836607296719 * 838784442581 * 871923615209 * 891152617007 * 944189993029 * 957027949433 * 992735373053 * 1036372987901 * 1057438303553"
qstr = "21312192379 * 41694776327 * 69102768037 * 86131058131 * 129887877181 * 144561148073 * 172718834527 * 183076580677 * 315959390353 * 359234858707 * 359289993437 * 472896378329 * 522484567589 * 558061439779 * 563426178853 * 616107638803 * 623193007529 * 686116305163 * 747518751157 * 750776132569 * 779700020551 * 784911464809 * 823394947451 * 854962951303 * 933107199179 * 1027411280821 * 1057330714703"
e = 65537

n = 0x820360637236294eca7338e8134f1fdc1ed3bfbc580556cfc3e162ca6c4d3f78388d838f2c02d3cd244b535c6c55573e137e9bfc2ed2543f597ac2704a0a5e9c38026d4e7ecc380b838a6a0c81364a918a9023914874900e4947ae78f8f0e4e7c1b19812356600febf8f4511124fdd2346e52561638360f71d3d1ca72a00b9126d8262e8e28e6e097fee8d84cf998d959da0586196d2b50e8bf64d1211da7979889a9054ba6be65ade326333cbdab0830bd10da162edbb440bc8f100bb0aba5a41c8ba57d94b197fa46e24cb1e4b24ca9e2ea6fc64bc8fd0c3c303d7878b2a74473e9a6d295fd4c168206db7f3dd46f489d43d4cffc0eeeabf72036c42cd80d1

p = map(int, pstr.split(" * "))
q = map(int, qstr.split(" * "))

print p
print q

phy = 1

for a in p:
	phy *= (a-1)

for a in q:
	phy *= (a-1)

print phy

d = modInv(e, phy)

print d

f = open("encrypted","rb")

c = f.read().encode("hex")

c = int("0x"+c,16)

m = pow(c, d, n)

h="0"+hex(m)[2:-1]

print h.decode("hex")

f.close()

# FLAG{4c7u4lly_N_c4n_b3_br0k3n}

